#ifndef __PIECEMEMPOOL_H__
#define __PIECEMEMPOOL_H__

#include <malloc.h>

const int PoolSize = 64*1024;

class PieceMemPoolHead
{
public:
	PieceMemPoolHead()
	{
		Prec=this;
		Next=this;
	}
public:
	PieceMemPoolHead* Prec;
	PieceMemPoolHead* Next;
};

class PieceMemPool : public PieceMemPoolHead
{
public:
	PieceMemPool(int Size){Init(Size);}
	~PieceMemPool(){Release();}
public:
	void Init(int Size);
	void Release();
	bool CanMalloc() {return mTotalElem>mUsedElem;}
	void* Malloc();
	void  Free(void* mem);
	int  GetSize() {return mSize;}
	bool IsElem(void* mem) 
	{
		return (mem>=mData&&mem<((char*)mData)+PoolSize);
	}
	void* GetData() {return mData;}
private:
	int mSize;
	int mTotalElem;
	int mUsedElem;
	void* mHead;
	void* mData;
};

const unsigned int DictBit = (sizeof(int)-2)/2;
const unsigned int DictSize = DictBit*256;

int log2(int v);

template<int MaxPoolSize>
class PieceMem
{
public:
	PieceMem() {InitPool();}
	~PieceMem() {Release();}
public:
	void InitPool();
	void Release();
	PieceMemPool** InitDict() {return new PieceMemPool*[DictSize];}
	PieceMemPool* CreateNewPool(int size);
	void* Malloc(int size);
	void Free(void* mem);
	void Relink(PieceMemPool* pool);
private:
	PieceMemPoolHead* mPoolMap[MaxPoolSize+1];
	PieceMemPoolHead* mPool;
	PieceMemPool** mPoolDict[DictSize];
};

template<int MaxPoolSize>
void PieceMem<MaxPoolSize>::InitPool()
{
	mPool = new PieceMemPoolHead[log2(MaxPoolSize-1)];

	for(int i=0;i<DictSize;i++)
	{
		mPoolDict[i]=(PieceMemPool**)0;
	}

	int poolsize=sizeof(void*);
	PieceMemPool* pool = CreateNewPool(poolsize);
	for(int i=0;i<=MaxPoolSize;i++)
	{
		if(i>poolsize)
		{
			poolsize*=2;
			pool = CreateNewPool(poolsize);
		}
		mPoolMap[i]=mPool+(log2(poolsize)-2);
	}
}

template<int MaxPoolSize>
void PieceMem<MaxPoolSize>::Release()
{
	int totalpoolcount = log2(MaxPoolSize-1);
	for(int i=0;i<totalpoolcount;i++)
	{
		while(mPool[i].Next!=mPool+i)
		{
			PieceMemPoolHead* delnode = mPool[i].Next;
			delnode->Next->Prec=&(mPool[i]);
			mPool[i].Next=delnode->Next;
			delete delnode;
		}

	}
}

template<int MaxPoolSize>
PieceMemPool* PieceMem<MaxPoolSize>::CreateNewPool(int size)
{
	PieceMemPool* ret = new PieceMemPool(size);
	unsigned int addr = (unsigned int)ret->GetData();
	PieceMemPool** &dict = mPoolDict[addr>>((DictBit+2)*8)];
	if(!dict)
		dict = InitDict();
	dict[(addr>>(2*8))&((1<<(DictBit*8))-1)] = ret;
	PieceMemPoolHead& poolptr = mPool[log2(size)-2];
	ret->Next=poolptr.Next;
	ret->Prec=&poolptr;
	poolptr.Next->Prec=ret;
	poolptr.Next=ret;
	return ret;
}

template<int MaxPoolSize>
void* PieceMem<MaxPoolSize>::Malloc(int size)
{
	if(size>MaxPoolSize)
		return malloc(size);
	if(size<=0)
		return 0;
	PieceMemPoolHead* head = mPoolMap[size];
	for(PieceMemPoolHead* node=head->Next;node!=head;node=node->Next)
	{
		PieceMemPool* pool = (PieceMemPool*)node;
		if(pool->CanMalloc())
		{
			Relink(pool);
			return pool->Malloc();
		}
	}
	PieceMemPool* pool = CreateNewPool(((PieceMemPool*)(head->Next))->GetSize());
	return pool->Malloc();
}

template<int MaxPoolSize>
void PieceMem<MaxPoolSize>::Free(void* mem)
{
	unsigned int addr = (unsigned int)mem;
	unsigned int dict1 = addr>>((DictBit+2)*8);
	unsigned int dict2 = (addr>>(2*8))&((1<<(DictBit*8))-1);
	PieceMemPool* pool = 0;
	if(mPoolDict[dict1])
	{
		if((mPoolDict[dict1][dict2]&&mPoolDict[dict1][dict2]->IsElem(mem))
			||(dict2>0&&mPoolDict[dict1][dict2-1]&&mPoolDict[dict1][dict2-1]->IsElem(mem)))
		{
			pool = mPoolDict[dict1][dict2];
		}
	}
	if(dict2==0&&dict1>0
		&&mPoolDict[dict1-1]
	&&mPoolDict[dict1-1][0xff]
	&&mPoolDict[dict1-1][0xff]->IsElem(mem))
	{
		pool = mPoolDict[dict1-1][0xff];
	}
	if(pool)
	{
		pool->Free(mem);
		Relink(pool);
	}
	else
	{
		free(mem);
	}
}

template<int MaxPoolSize>
void PieceMem<MaxPoolSize>::Relink(PieceMemPool* pool)
{
	PieceMemPoolHead* head = mPoolMap[pool->GetSize()];
	if(head->Next!=pool)
	{
		if(!((PieceMemPool*)head->Next)->CanMalloc())
		{
			pool->Next->Prec=pool->Prec;
			pool->Prec->Next=pool->Next;
			pool->Next=head->Next;
			pool->Prec=head;
			head->Next->Prec=pool;
			head->Next=pool;
		}
	}
}


extern PieceMem<1024> GPieceMem;


#endif
